package graph;

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @Author: LDeng
 * @Date: 2021-04-02 10:27
 */
public abstract class Graph<V, E> {

    protected WeightManager<E> weightManager;

    public Graph() {

    }

    public Graph(WeightManager<E> weightManager){
        this.weightManager=weightManager;
    }


    public abstract int edgesSize();

    public abstract int verticesSize();

    //添加一个顶点
    public abstract void addVertex(V v);

    //添加一条边(有权值/没有权值)
    public abstract void addEdge(V from, V to);

    public abstract void addEdge(V from, V to, E weight);

    //删除一个顶点
    public abstract void removeVertext(V v);

    //删除一条边
    public abstract void removeEdge(V from, V to);

    //广度优先遍历
    public abstract  void bfs(V begin,VertexVisitor<V> visitor);

    //深度优先遍历
    public abstract void dfs(V begin,VertexVisitor<V> visitor);

    public interface VertexVisitor<V>{
        boolean visit(V v);
    }

    //有向无环图 的拓扑排序，
    public abstract List<V> toplogcalSort();

    //最小生成树
    public abstract Set<EdgeInfo<V,E>> mst();

    //最短路径Map 存放起点到其他点的距离信息
    //public abstract Map<V,E> shortestPath(V begin);
    //单源最短路径算法（Dijstra/Bellman-ford）
    public abstract Map<V,PathInfo<V,E>> shortestPath(V begin);

    //多源最短路径(Floyd)
    public abstract Map<V,Map<V,PathInfo<V,E>>> shortestPath();



    public interface WeightManager<E>{
        int compare(E w1,E w2);
        E add(E w1,E w2);
        E zero();
    }

    public static class PathInfo<V,E>{
        protected E weight;
        protected List<EdgeInfo<V,E>> edgeInfos=new LinkedList<>();//使用Linkedlist确保是有序的

        public PathInfo() {}
        public PathInfo(E weight) {
            this.weight = weight;
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }

        public List<EdgeInfo<V, E>> getEdgeInfos() {
            return edgeInfos;
        }

        public void setEdgeInfos(List<EdgeInfo<V, E>> edgeInfos) {
            this.edgeInfos = edgeInfos;
        }

        @Override
        public String toString() {
            return "PathInfo{" +
                    "weight=" + weight +
                    ", edgeInfos=" + edgeInfos +
                    '}';
        }
    }

   public static class EdgeInfo<V,E>{
        private V from;
        private V to;
        private E weight;

        public EdgeInfo(V from, V to, E weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public V getFrom() {
            return from;
        }

        public void setFrom(V from) {
            this.from = from;
        }

        public V getTo() {
            return to;
        }

        public void setTo(V to) {
            this.to = to;
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "EdgeInfo{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }
}
